package demo1;

public class HashBucket {
    static class Node {
        public int key;
        public int val;
        public Node next;

        public Node(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }

    private Node[] list;
    private int usedSize;
    private static final float OVER_LOAD_FACTORY = 0.75f;

    public HashBucket() {
        this.list = new Node[10];
    }

    // 添加
    public void put(int key, int val) {
        int index = key % list.length;
        // 遍历
        Node cur = list[index];
        Node prev = null;
        while(cur != null) {
            if(cur.key == key) {
                // 关键字相同 更新
                cur.val = val;
                return;
            }
            prev = cur;
            cur = cur.next;
        }

        // cur == null --> 找不到
        if(prev == null) {
            // 说明该位置一个都没有
            list[index] = new Node(key, val);
        } else {
            prev.next = new Node(key, val);
        }
        usedSize++;

        if(getLoadFactory() >= OVER_LOAD_FACTORY) {
            // 重新调整
            resize();
        }
    }

    private void resize() {
        Node[] tmpList = new Node[list.length * 2];

        // 遍历
        for (int i = 0; i < list.length; i++) {
            Node cur = list[i];

            while(cur != null) {
                int index = cur.key % tmpList.length;
                Node next = cur.next;// 用来存储 cur 的下一个防止找不到
                // 尾插
                Node tmp = tmpList[index];
                while(tmp != null && tmp.next != null) {
                    tmp = tmp.next;
                }
                if(tmp == null) {
                    tmpList[index] = cur;
                } else {
                    tmp.next = cur;
                }
                cur.next = null;// 考虑 cur 是新数组的最后一个且不是旧的数组的最后一个
                cur = next;
            }
        }

        list = tmpList;
    }

    // 获取元素
    public int get(int key) {
        int index = key % list.length;
        Node cur = list[index];
        while(cur != null) {
            if(cur.key == key) {
                return cur.val;
            }
            cur = cur.next;
        }
        return -1;
    }

    // 得到 超载因子
    private float getLoadFactory() {
        return usedSize * 1.0f / list.length;
    }
}
